public class practice3 {

//    Top 101 实现两个有序链表的合并

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {

        // 针对这里的两个链表的合并操作，不能单纯的思考为 以某一个链表为基准让另一个链表插入，会复杂化这个问题
        // 可以创建出一个空的头结点，重新连接出来一个新的链表
        // 先来定义出一个节点
        // 这里的值都是大于 0 的，在这里将节点中的值设定为 -1
        ListNode node = new ListNode(-1);
        ListNode p = node;
        // 针对两个链表进行比较
        while(pHead1 != null && pHead2 != null) {
            if(pHead1.val <= pHead2.val) {
                node.next = pHead1;
                pHead1 = pHead1.next;
                node = node.next;
            }else {
                node.next = pHead2;
                pHead2 = pHead2.next;
                node = node.next;
            }
        }

        // 在上面的判断中，只要有一个链表出现 null 就会直接跳出循环，但是另一个链表不一定处理完毕了
        // 这里需要单独处理一下
        if(pHead1 == null) {
            // 此时就将 pHead2 后面的值接到后面
            node.next = pHead2;
        }
        if(pHead2 == null) {
            node.next = pHead1;
        }
        // write code here
        // 这里的返回值是需要排除自己创建的第一个元素的
        return p.next;
    }
}
